package com.binaryTree;

public class DeleteNodeinaBST0306_450 {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return null;

        if(root.val > key) root.left = deleteNode(root.left, key);
        if(root.val < key) root.right = deleteNode(root.right, key);

        if(root.val == key) {
            if (root.left == null && root.right != null) return root.right;
            if (root.left != null && root.right == null) return root.left;
            if (root.left == null && root.right == null) return null;
            //root左右都不空
            turnTree(root.left, root.right);
            return root.right;
        }

        return root;
    }

    private void turnTree(TreeNode left, TreeNode right) {
        TreeNode node = right;
        while (node.left != null){
            node = node.left;
        }
        node.left = left;
    }
}
